ECE1724 - Assignment 2¶

Prepared by Talha Alvi and Farhan Wadia

Question 1¶

There are various criteria, hard and soft constraints that can be considered in a delivery vehicle routing optimization problem. An additional criteria for routing would be route selection that minimizes fuel usage. This can be done by considering the average speeds along the route and using the delivery vehicle fuel consumption figures to calculate the most fuel efficient route. A hard constraint that can be considered is that the deliveries must co-incide with the opening hours of each place of business. This makes the problem even more challenging as separate time windows will need to be considered for each business. Other constraints include maximum weight or volume that can be carried by the delivery vehicle, before it may need to return to the warehouse to load more items. Another soft constraint would be to avoid certain routes during rush hour to minimize delivery times. A soft constraint that can be imposed on the problem is to avoid routing through school zones or residential zones to avoid creating congestion or creating noise pollution in quite areas.

Question 2¶

In [ ]:
import pandas as pd

# Import the dataset
df = pd.read_csv('GTA Delivery Dataset\GTA Delivery Data.csv')
In [ ]:
# Obtain the unique collection (source) locations and how many dropoff locations each serves
collection_locations = df.groupby(['collection_lat', 'collection_lng']).size().reset_index().rename(columns={0:'Dropoff Locations Count'})
collection_locations
Out[ ]:
collection_lat collection_lng Dropoff Locations Count
0 43.643481 -79.399857 1
1 43.805779 -79.518231 115
2 43.838713 -79.315498 59
In [ ]:
import numpy as np
import folium

# Plot the locations on a map

# Define center point for map
avg_lat = np.average(df[['collection_lat', 'dropoff_lat']].values.flatten())
avg_lng = np.average(df[['collection_lng', 'dropoff_lng']].values.flatten())
center = (avg_lat, avg_lng)

m = folium.Map(location=center, zoom_start=8.5)

# Define dropoff marker colours corresponding to each collection location
dropoff_colours =['green', 'orange', 'purple']

for collection_location_index, collection_location_row in collection_locations.iterrows():
    # Plot collection locations with blue marker and icon colour corresponding to dropoff locations
    filtered = df[df["collection_lat"] == collection_location_row['collection_lat']]
    
    folium.Marker(location=(collection_location_row['collection_lat'], collection_location_row['collection_lng']),
                  icon=folium.Icon(icon='car', color='blue', icon_color=dropoff_colours[collection_location_index], prefix='fa'),
                  tooltip = str(collection_location_row['collection_lat']) + "," + str(collection_location_row['collection_lng'])).add_to(m)
        
    #Plot dropoff locations in colours corresponding to source (i.e. collection location)
    for index, row in filtered.iterrows():       
        folium.Marker(location=(row['dropoff_lat'], row['dropoff_lng']),
                  icon=folium.Icon(icon='map-pin', color=dropoff_colours[collection_location_index], prefix='fa'),
                  tooltip = str(row['dropoff_lat']) + "," + str(row['dropoff_lng'])).add_to(m)
    
m
Out[ ]:
Make this Notebook Trusted to load map: File -> Trust Notebook

Question 3¶

Choose Navigation Points¶

In [ ]:
# Arbitrarily pick the 3rd source and the locations at (43.8256628, -79.3993708) and (43.8543771, -79.4699297)
source = (collection_locations["collection_lat"].iloc[2], collection_locations["collection_lng"].iloc[2])
dest1 = (43.8256628, -79.3993708)
dest2 = (43.8543771, -79.4699297)

# Plot the locations for reference
m = folium.Map(location=source, zoom_start=12)
folium.Marker(location=source,icon=folium.Icon(color='purple',icon='car', prefix='fa')).add_to(m)
folium.Marker(location=dest1,icon=folium.Icon(color='purple',icon='map-marker', prefix='fa')).add_to(m)
folium.Marker(location=dest2,icon=folium.Icon(color='purple',icon='map-marker', prefix='fa')).add_to(m)

m
Out[ ]:
Make this Notebook Trusted to load map: File -> Trust Notebook

Convert Road Network to Graph¶

In [ ]:
import geopandas as gpd
import osmnx
import math

#Load a geojson file created using geojson.io to define the graph boundaries (Dufferin-Major Mackenzie to Kennedy-Steeles)
boundary_geojson = gpd.read_file('q3_boundary.geojson')
graph = osmnx.graph_from_polygon(boundary_geojson.geometry[0], network_type='drive', simplify=True, clean_periphery=True)

# Plot the graph
osmnx.plot_graph(graph,figsize=(10,10))
Out[ ]:
(<Figure size 1000x1000 with 1 Axes>, <AxesSubplot: >)

Find Graph Nodes Closest to Navigation Points¶

In [ ]:
import geopandas

# Find closest graph nodes to source and destinations
X = [source[1], dest1[1], dest2[1]]
Y = [source[0], dest1[0], dest2[0]]
closest_nodes = osmnx.distance.nearest_nodes(graph,X,Y)

# Get the rows from the Node GeoDataFrame
nodes, edges = osmnx.graph_to_gdfs(graph)
closest_rows = nodes.loc[closest_nodes]

# Put the nodes into a GeoDataFrame
od_nodes = geopandas.GeoDataFrame(closest_rows, geometry='geometry', crs=nodes.crs)
od_nodes
Out[ ]:
y x highway street_count ref geometry
osmid
319291881 43.836227 -79.315404 turning_circle 1 NaN POINT (-79.31540 43.83623)
446439005 43.825711 -79.400226 NaN 3 NaN POINT (-79.40023 43.82571)
297839692 43.853195 -79.469145 NaN 3 NaN POINT (-79.46915 43.85319)
In [ ]:
# Plot map with original points (purple), graph vertices for navigation (red), and the graph

osmnx.folium.plot_graph_folium(graph, graph_map=m)

folium.Marker(location=source,icon=folium.Icon(color='purple',icon='car', prefix='fa')).add_to(m)
folium.Marker(location=dest1,icon=folium.Icon(color='purple',icon='map-marker', prefix='fa')).add_to(m)
folium.Marker(location=dest2,icon=folium.Icon(color='purple',icon='map-marker', prefix='fa')).add_to(m)


folium.Marker(location=(od_nodes["y"].iloc[0], od_nodes["x"].iloc[0]),icon=folium.Icon(color='red',icon='car', prefix='fa')).add_to(m)
folium.Marker(location=(od_nodes["y"].iloc[1], od_nodes["x"].iloc[1]),icon=folium.Icon(color='red',icon='map-marker', prefix='fa')).add_to(m)
folium.Marker(location=(od_nodes["y"].iloc[2], od_nodes["x"].iloc[2]),icon=folium.Icon(color='red',icon='map-marker', prefix='fa')).add_to(m)

m
Out[ ]:
Make this Notebook Trusted to load map: File -> Trust Notebook

Dijkstra¶

Implement Dijkstra shortest path using networkx

In [ ]:
import networkx as nx
from datetime import datetime
from smart_mobility_utilities.common import cost

#Source -> d1 -> d2 path
start = datetime.now()
source_to_d1 = nx.shortest_path(G=graph,source=closest_nodes[0],target=closest_nodes[1], weight='length', method='dijkstra')
d1_to_d2 = nx.shortest_path(G=graph,source=closest_nodes[1],target=closest_nodes[2], weight='length', method='dijkstra')
route1_dijkstra = source_to_d1[:-1] + d1_to_d2
route1_dijkstra_time = datetime.now() - start


#Source -> d2 -> d1 path
start = datetime.now()
source_to_d2 = nx.shortest_path(G=graph,source=closest_nodes[0],target=closest_nodes[2], weight='length', method='dijkstra')
d2_to_d1 = nx.shortest_path(G=graph,source=closest_nodes[2],target=closest_nodes[1], weight='length', method='dijkstra')
route2_dijkstra = source_to_d2[:-1] + d2_to_d1
route2_dijkstra_time = datetime.now() - start

Source -> D1 -> D2 path¶

In [ ]:
# Plot source -> d1 -> d2 (green)
osmnx.plot_graph_route(graph, route=route1_dijkstra, route_color='g', figsize=(10,10))
Out[ ]:
(<Figure size 1000x1000 with 1 Axes>, <AxesSubplot: >)
In [ ]:
print("Source to D1 Cost:", cost(graph, source_to_d1))
print("D1 to D2 Cost:", cost(graph, d1_to_d2))
print("Route 1 Cost:", cost(graph, route1_dijkstra))
print("Route 1 Execution Time:", route1_dijkstra_time)

Source to D1 Cost: 10024.849
D1 to D2 Cost: 8977.816
Route 1 Cost: 19002.665
Route 1 Execution Time: 0:00:00.021965

Although the route from source -> d1 -> d2 is expected to have a lower cost than the route from source -> d2 -> d1, check the latter as a reference.

Source -> D2 -> D1 path¶

In [ ]:
# Plot source -> d2 -> d1 (blue)
osmnx.plot_graph_route(graph, route=route2_dijkstra, route_color='b', figsize=(10,10))
Out[ ]:
(<Figure size 1000x1000 with 1 Axes>, <AxesSubplot: >)
In [ ]:
print("Source to D2 Cost:", cost(graph, source_to_d2))
print("D2 to D1 Cost:", cost(graph, d2_to_d1))
print("Route 2 Cost:", cost(graph, route2_dijkstra))
print("Route 2 Execution Time:", route2_dijkstra_time)

Source to D2 Cost: 16052.899
D2 to D1 Cost: 8927.946
Route 2 Cost: 24980.845
Route 2 Execution Time: 0:00:00.035998

Simulated Annealing¶

The implementation of simulated annealing below is based on https://smartmobilityalgorithms.github.io/book/content/TrajectoryAlgorithms/SimulatedAnnealing.html. Only the path from source -> d1 -> d2 will be considered for the work below.

The neighbour_function for the simulated annealing has been modified to be based on randomized_search rather than get_children to reduce the execution time required. Additionally, the simulated_annealing function has been modified to return the lowest cost route based on all of the iterations rather than the last executed iteration.

In [ ]:
from smart_mobility_utilities.common import randomized_search, cost # from https://github.com/SmartMobilityAlgorithms/smart_mobility_utilities
from smart_mobility_utilities.children import get_children
import random
from smart_mobility_utilities.common import probability
from tqdm.notebook import tqdm
import networkx

def exp_schedule(k=20, lam=0.005, limit=100):
    function = lambda t: (k * np.exp(-lam*t) if t<limit else 0)
    return function

def get_neighbours_route(G, route):
    # Generate more paths to choose from
    neighbours = get_children(G,route,num_children=1)
    return random.choice(neighbours)

def get_neighbours_random(G, route):
    # generate 5 more random paths to choose from and arbitrarily select one of them
        neighbours = list()
        for _ in range(5):
            child = randomized_search(G, route[0], route[-1])
            neighbours.append(child)
        return random.choice(neighbours)

def simulated_annealing(G, initial_solution, num_iter, schedule_function, neighbour_function, cost_function, use_tqdm=False):
    current = initial_solution
    states = [cost_function(G,initial_solution)]
    
    best_state = states[0]
    best_solution = current
    
    if use_tqdm: pbar = tqdm(total=num_iter)
    for t in range(num_iter):
        if use_tqdm: pbar.update()
        T = schedule_function(t)
        next_choice = neighbour_function(G,current)
        current_cost = cost_function(G, current)
        next_cost = cost_function(G, next_choice)
        delta_e = next_cost - current_cost
        if delta_e < 0 or probability(np.exp(-1 * delta_e / T)):
            current = next_choice
        states.append(cost_function(G, current))
        
        if states[-1] < best_state:
            best_state = states[-1]
            best_solution = current
    
    return best_solution, best_state, states

Source to Destination 1¶

In [ ]:
solution_random_1 = randomized_search(graph, od_nodes.iloc[0].name, od_nodes.iloc[1].name)

print("Initial Solution:", solution_random_1)
print("Initial Cost:", cost(graph, solution_random_1))

Initial Solution: [319291881, 319291589, 319291583, 428078263, 428078250, 1087663336, 1087663391, 2617927126, 319093663, 1087663331, 319095278, 319095289, 1695514658, 29659606, 29659801, 29659607, 1765426021, 29660127, 29659614, 383282982, 312075233, 251723323, 251714055, 708829335, 9051301531, 1764425395, 1764425391, 1764425384, 414445562, 446426163, 2605260156, 2605258704, 446426223, 446426162, 446426225, 320255563, 446438824, 446439005]
Initial Cost: 11048.363
In [ ]:
osmnx.plot_graph_route(graph,solution_random_1,figsize=(10,10))
Out[ ]:
(<Figure size 1000x1000 with 1 Axes>, <AxesSubplot: >)
In [ ]:
start = datetime.now()

num_iterations = 750
schedule = exp_schedule(k=1000, lam=0.005, limit=num_iterations)

solution_sa_1, cost_sa_1, states_sa_1 = simulated_annealing(
    graph,
    solution_random_1,
    num_iterations,
    schedule,
    get_neighbours_random,
    cost,
    use_tqdm=True
)

source_to_d1_SA_time = datetime.now() - start

print("SA Solution:", solution_sa_1)
print("SA Cost:", cost_sa_1)
print("Execution Time:", source_to_d1_SA_time)

  0%|          | 0/750 [00:00<?, ?it/s]
SA Solution: [319291881, 319291589, 319291583, 428078263, 319291716, 35229563, 35228959, 35228958, 2604969377, 35228734, 2604951677, 2604948472, 251214464, 1735886246, 1735886245, 1735886243, 1735886227, 414475392, 296401810, 439333819, 439333839, 439333789, 439334076, 318960742, 439334114, 439334062, 296401815, 439334070, 302958692, 6593997905, 414428356, 446455833, 1722084143, 1722084138, 446455896, 446455868, 446462897, 321551698, 446470365, 446470374, 318814585, 446470369, 446426228, 446426225, 320255563, 446438824, 446439005]
SA Cost: 9103.723
Execution Time: 0:04:36.943120
In [ ]:
osmnx.plot_graph_route(graph,solution_sa_1,figsize=(10,10))
Out[ ]:
(<Figure size 1000x1000 with 1 Axes>, <AxesSubplot: >)
In [ ]:
import matplotlib.pyplot as plt

plt.xlabel("Number of Iterations")
plt.ylabel("Trip Cost (m)")
plt.title("Trip Cost (m) vs. Number of iterations")
plt.plot(states_sa_1)
plt.show()

Destination 1 to Destination 2¶

In [ ]:
solution_random_2 = randomized_search(graph, od_nodes.iloc[1].name, od_nodes.iloc[2].name)

print("Initial Solution:", solution_random_2)
print("Initial Cost:", cost(graph, solution_random_2))

Initial Solution: [446439005, 321085647, 320255563, 446426225, 446426223, 2605258704, 2605260156, 446426163, 414445562, 1764425384, 1764425392, 1764425395, 9051301531, 708829344, 251723299, 708829627, 251723308, 29659616, 29659618, 383283020, 88576351, 88576417, 61569180, 88576277, 319267896, 319269214, 5951111973, 319269203, 708693285, 319269341, 414425541, 319269336, 288368992, 288368991, 288368990, 414446269, 414470653, 1362143842, 287475544, 288368983, 288514566, 618752587, 288514561, 414424722, 302948593, 302948590, 302948581, 288514544, 288368056, 288368055, 287172829, 7737766287, 7737766277, 7737766273, 683402201, 414443286, 414408578, 683402175, 1089432082, 1089432155, 297839692]
Initial Cost: 10882.158
In [ ]:
osmnx.plot_graph_route(graph,solution_random_2,figsize=(10,10))
Out[ ]:
(<Figure size 1000x1000 with 1 Axes>, <AxesSubplot: >)
In [ ]:
start = datetime.now()

solution_sa_2, cost_sa_2, states_sa_2 = simulated_annealing(
    graph,
    solution_random_2,
    num_iterations,
    schedule,
    get_neighbours_random,
    cost,
    use_tqdm=True
)

d1_to_d2_SA_time = datetime.now() - start

print("SA Solution:", solution_sa_2)
print("SA Cost:", cost_sa_2)
print("Execution Time:", d1_to_d2_SA_time)

  0%|          | 0/750 [00:00<?, ?it/s]
SA Solution: [446439005, 321085647, 320255563, 446426225, 446426223, 2605258704, 2605260156, 446426163, 414445562, 1764425384, 1764425392, 1764425395, 9051301531, 708829344, 251723299, 708829627, 251723308, 29659616, 29659618, 383283020, 88576351, 88576417, 61569180, 3722039434, 9492871737, 61569188, 9492871793, 9492871755, 7894424881, 7894424879, 304966133, 414422292, 288368990, 414446269, 414470653, 1362143842, 287475544, 1362147964, 414437790, 1362147950, 1853256834, 287475546, 1700509655, 1700509661, 288514552, 288514551, 1700509703, 1700509725, 302947182, 287172828, 7737766227, 287478743, 1089432168, 1627887898, 1627887908, 287479248, 414419538, 1089432128, 1089432155, 297839692]
SA Cost: 9520.824
Execution Time: 0:10:09.125361
In [ ]:
osmnx.plot_graph_route(graph,solution_sa_2,figsize=(10,10))
Out[ ]:
(<Figure size 1000x1000 with 1 Axes>, <AxesSubplot: >)
In [ ]:
plt.xlabel("Number of Iterations")
plt.ylabel("Trip Cost (m)")
plt.title("Trip Cost (m) vs. Number of iterations")
plt.plot(states_sa_2)
plt.show()

Simulated Annealing Route¶

In [ ]:
sa_route = solution_sa_1[:-1] + solution_sa_2
print("Simulated Annealing Route Cost:", cost(graph, sa_route))
print("Simulated Annealing Route Execution Time:", source_to_d1_SA_time + d1_to_d2_SA_time)

Simulated Annealing Route Cost: 18624.547
Simulated Annealing Route Execution Time: 0:14:46.068481
In [ ]:
osmnx.plot_graph_route(G=graph, route=sa_route, route_color='g', figsize=(10,10))
Out[ ]:
(<Figure size 1000x1000 with 1 Axes>, <AxesSubplot: >)

Comparison of Algorithms¶

The table below summarizes the route lengths and computation times found using Dijkstra and the Simulated Annealing algorithms.

Algorithm Route Distance (m) Execution Time (s)
Dijkstra 19003 0.02
Simulated Annealing 18625 886

Although Dijkstra runs significantly faster than Simulated Annealing, the latter was able to provide a slightly better route (378 m shorter), without requiring an overbearing amount of time for execution (<15 mins). By probabilistically accepting solutions that are slightly worse between iterations, Simulated Annealing is able to explore more broadly over the solution space before it starts converging to a given solution. On the other hand, the results from using Djikstra are deterministic and based on searching in a structured, greedy fashion. The implementations of Dijkstra and Simulated Annealing also likely played a role in the execution time for Dijkstra being better; the networkx method used for Dijkstra would be expected to be more computationally optimized than the Simulated Annealing implementation used here.

In summary, comparing these two algorithms shows that there is a tradeoff between computation time and obtaining lower cost solutions. For an application like Google Maps, the simulated annealing approach would take far too long and frustrate users, so Djikstra would be the better algorithm choice. For a small-size Delivery Service Provider (DSP) as described in the problem statement, Simulated Annealing might be a better algorithm choice since it can be assumed that sufficient time exists between the destinations becoming known to the DSP and actually having to execute the deliveries (allowing for computation time), and that the goal is to minimize route distances.

The map below shows the source and destination locations (purple), their closest corresponding nodes on the network graph (orange), and the routes found by each algorithm (red for Dijkstra and blue for Simulated Annealing).

In [ ]:
m = folium.Map(location=source, zoom_start=12)

folium.Marker(location=source,icon=folium.Icon(color='purple',icon='car', prefix='fa')).add_to(m)
folium.Marker(location=dest1,icon=folium.Icon(color='purple',icon='map-marker', prefix='fa')).add_to(m)
folium.Marker(location=dest2,icon=folium.Icon(color='purple',icon='map-marker', prefix='fa')).add_to(m)

folium.Marker(location=(od_nodes["y"].iloc[0], od_nodes["x"].iloc[0]),icon=folium.Icon(color='orange',icon='car', prefix='fa')).add_to(m)
folium.Marker(location=(od_nodes["y"].iloc[1], od_nodes["x"].iloc[1]),icon=folium.Icon(color='orange',icon='map-marker', prefix='fa')).add_to(m)
folium.Marker(location=(od_nodes["y"].iloc[2], od_nodes["x"].iloc[2]),icon=folium.Icon(color='orange',icon='map-marker', prefix='fa')).add_to(m)

osmnx.plot_route_folium(G=graph, route=sa_route, route_map=m, color='#0000FF', opacity=0.5) 
osmnx.plot_route_folium(G=graph, route=route1_dijkstra, route_map=m, color='#FF0000', opacity=0.5) 

m
Out[ ]:
Make this Notebook Trusted to load map: File -> Trust Notebook